package Algorithm.dynamicProgramming.knapsackDp;

/**
 * 01背包基础问题：
 * 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解能装入背包里物品最大价值总和。
 * 背包问题分类：1. 最大/最小价值问题 2. 存在问题 3. 组合问题：求所有满足……的排列组合
 * 视频讲解：https://www.bilibili.com/video/BV1pY4y1J7na
 */
public class KnapsackBasic {

    /**
     * 1. 定义dp：dp[i][j]为背包容量为j时从前i件物品中选取能获得的最大价值
     * 2. 状态转移公式：对于dp[i][j]可分为以下两种情况，故dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1])
     *              （1）当不选第i件物品时，dp[i][j]即为容量j从前i-1件物品中选取能获得的最大价值dp[i-1][j]
     *              （2）当选第i件物品时，dp[i][j] = value[i-1] + dp[i-1][j-weight[i-1]]
     * 3. 初始化：dp[0][j]=0;dp[i][0]=0
     * 4. 递推：从上到下逐层遍历
     */
    public int knapsackBasic(int[] weight, int[] value, int w) {
        int[][] dp = new int[weight.length+1][w+1];
        for (int i = 1;i <= weight.length;i++) {
            for (int j = 1;j <= w;j++) {
                if (weight[i-1] > j) //必须判断第i件物品重量是否直接超过了j
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = Math.max(dp[i-1][j], value[i-1]+dp[i-1][j-weight[i-1]]);//这里第i件物品在weight和value数组中的下标为i-1
            }
        }
        return dp[weight.length][w];
    }


    /**
     * 优化：滚动数组。通过分析发现，每一层中的dp[i][j]只和上一层中j及其左边的数据有关，故可只用一个一维数组dp[j]来表示上一层的数据，
     *      在遍历当前层时倒序遍历（若正序遍历则刷新会覆盖后续元素要用到的上一层数据）滚动刷新dp[j]
     * 1. 定义dp：dp[j]为一层中背包容量为j时能获得的最大价值
     * 2. 状态转移公式：在当前层中d[j] = max(d[j], d[j-weight[i]]+value[i]) 此时d[j]和d[j-weight[i]]都是上一层中的数据
     * 3. 初始化：初始在第0层，dp[]全为0
     * 4. 递推：从上到下逐层遍历 每一层中采用倒序遍历
     */
    public int knapsackBasic2(int[] weight, int[] value, int w) {
        int[] dp = new int[w+1];
        for (int i = 0;i < weight.length;i++) {
            for (int j = w;j >= weight[i];j--) { //倒序遍历，注意j必须大于等于weight[i] 小于weight[i]的dp[j]必定和上一层相同 所以不用动
                dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
            }
        }
        return dp[w];
    }
}
